package com.leetcode;
import java.util.Arrays;
/**
 * @author LongYu
 * @date 2022/7/27 10:28
 */
public class D_62 {
    public static void main(String[] args) {
//        int i = new D_62().uniquePaths(3, 2);
        int j = new D_62().uniquePaths3(3, 7);
        System.out.println(j);
    }
    public int uniquePaths3(int m, int n) {
        int min = Math.min(m, n);
        int max = Math.max(m, n);


        int[] ints = new int[min];
//        初始化
        Arrays.fill(ints, 1);

        while (--max > 0){
            for (int i = 1; i < min; i++) {
                ints[i] += ints[i-1];
            }
        }
        return ints[min-1];
    }



    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }



    public int uniquePaths1(int m, int n) {
        int[][] ints = new int[n][m];
        for (int i = 0; i < ints.length; i++) {
            for (int i1 = 0; i1 < ints[i].length; i1++) {
                if (i == 0 || i1 == 0){
                    ints[i][i1] = 1;
                    continue;
                }
                ints[i][i1] = ints[i-1][i1] + ints[i][i1-1];
            }
        }
        return ints[n-1][m-1];
    }

    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];

        for(int i = 0;i < n; i ++) {
            dp[i] = 1;
        }

        while (--m > 0) {
            for(int i = 1;i < n;i ++) {
                dp[i] += dp[i-1];
            }
        }

        return dp[n-1];
    }
}